# coding: utf8
# datetime: 2021-04-17
# 题目地址: https://leetcode-cn.com/problems/contains-duplicate-iii/

from typing import List

class Solution:
    # def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
    #     len_nums = len(nums)
    #     if len_nums < 2:
    #         return False
    #     for i in range(len_nums):
    #         # 区域划分
    #         tmp_nums = sorted(nums[i: i+k+1], key=lambda x: x)
    #         len_tmp = len(tmp_nums)
    #         if len_tmp < 2:
    #             break
    #         for j in range(len_tmp-1):
    #             if abs(tmp_nums[j]-tmp_nums[j+1]) <= t:
    #                 return True
    #     return False

    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        len_nums = len(nums)
        if len_nums < 2:
            return False
        for i in range(len_nums):
            # 区域划分
            tmp_nums = sorted(nums[i: i+k+1], key=lambda x: x)
            len_tmp = len(tmp_nums)
            if len_tmp < 2:
                break
            for j in range(len_tmp-1):
                if abs(tmp_nums[j]-tmp_nums[j+1]) <= t:
                    return True
        return False

a = Solution()
print(a.containsNearbyAlmostDuplicate([2147483640,2147483641], 1, 100))